package com.fengdi.solutions.hard;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author FengDi
 * @Description 给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
 * 整数除法仅保留整数部分。
 * 你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。
 * @Solution 将中缀表达式转换为后缀表达式，然后采用后缀表达式的求解方法进行求解
 * */
public class _227_basic_computer {
    // 运算符映射
    private final static Map<Character, Integer> map = new HashMap<>(){
        {
            put('-', 1);
            put('+', 1);
            put('*', 2);
            put('/', 2);
            put('^', 3);
            put('%', 3);
        }
    };

    public int calculate(String s) {
        s = s.replaceAll(" ", "");
        char[] chars = s.toCharArray();
        int len = s.length();

        Stack<Integer> nums = new Stack<>();
        nums.addLast(0);
        Stack<Character> ops = new Stack<>();
        this.init(nums, ops, chars, len);
        return nums.pop();
    }

    private void init(Stack<Integer> nums, Stack<Character> ops, char[] chars, int len) {
        if(chars.length == 0) return;
        for(int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if(c == '(') {
                ops.push(c);
            }else if(c == ')'){
                while(!ops.isEmpty()) {
                    if(ops.peek() != '(') {
                        this.calc(nums, ops);
                    }else {
                        ops.pop();
                        break;
                    }
                }
            }else {
                if (this.isDigit(c)) {
                    int j = i;
                    StringBuilder numberString = new StringBuilder();
                    while (j < len && isDigit(chars[j])) {
                        numberString.append(chars[j++]);
                    }
                    nums.push(Integer.parseInt(numberString.toString()));
                    i = j - 1;
                }else {
                    if (i > 0 && (chars[i - 1] == '(' || chars[i - 1] == '+' || chars[i - 1] == '-')) { 
                        nums.push(0);
                    }

                    while(!ops.isEmpty() && ops.peek() != '(') {
                        char prev = ops.peek();
                        if(map.get(prev) >= map.get(c)) {
                            this.calc(nums, ops);
                        }else {
                            break;
                        }
                    }
                    ops.push(c);
                }
            }
        }
        // 计算栈内所有的剩余元素
        while (!ops.isEmpty()) this.calc(nums, ops);
    }

    private void calc(Stack<Integer> nums, Stack<Character> ops) {
        if(nums.isEmpty() || nums.size() < 2) return;
        if(ops.isEmpty()) return;
        int x = nums.pop();
        int y = nums.pop();
        char op = ops.pop();
        int ans = basic_calc(x, y, op);
        nums.push(ans);
    }
    
    private int basic_calc(int x, int y, char op) {
        return switch (op) {
            case '+' -> x + y;
            case '-' -> y - x;
            case '*' -> x * y;
            case '/' -> y / x;
            case '^' -> (int) Math.pow(y, x);
            case '%' -> y % x;
            default -> 0;
        };
    }


    /**
     * @param c: 需要判断的字符
     * @return 字符是否是数字
     * */
    private boolean isDigit(char c) {
        return Character.isDigit(c);
    }

}
